Сайт Информационных Технологий

ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ ФУНКЦИОНАЛЬНОГО ПРЕОБРАЗОВАНИЯ ДЛЯ ОТКАЗОУСТОЙЧИВЫХ СЛЕДЯЩИХ СИСТЕМ

Н.М. Сафьянников, О.И.Буренева

Санкт-Петербургский государственный электротехнический университет “ЛЭТИ”

Abstract — The principles of computing algorithms organization which have genetic properties are proposed. The calculations in such algorithms are not considered events associated with the result obtaining but are represented in process form. Approaches to the construction of functional conversion genetic algorithms used in fault-tolerant trace systems are suggested. They are based on time slicing and time sweep of processes and parallel – serial informative stream organization. The computing architecture examples which confirm automatic result regeneration are adduced.

В отказоустойчивых следящих системах находят применение аппаратные преобразователи времяимпульсных сигналов со структурной организацией вычислительных процессов с отрицательной обратной связью. При этом обеспечивается автоматическое восстановление процесса вычисления при сбоях. Использование особенностей процессов, протекающих в подобных устройствах, позволило разработать ряд структуроподобных алгоритмов с сохранением устойчивости к помехам и нарушениям в работе отдельных ветвей процесса. Автоматический возврат к результату обеспечивается благодаря способности восстановления, заложенной в генетической организации алгоритма.

Структурно алгоритмы соответствуют саморазворачивающимся процессам с отрицательной обратной связью, которые стремятся к устойчивому состоянию, характеризующему конечный результат. При этом отсутствует пооперационное вычисление, а различные математические преобразования получаются в едином процессе формирования решения.

Рассматриваемые подходы к построению и анализу генетических алгоритмов функционального преобразования для отказоустойчивых следящих систем базируются на квантовании и временной развертке процессов, организации параллельно-последовательных информационных потоков.

В функциональном преобразовании множительно-делительная зависимость

Nвых=N N1 / N2

относится к базовым операторам и на ее примере можно проследить особенности работы предлагаемых генетических алгоритмов. Схема процесса множительно-делительного преобразования представлена на рис.1.

В основу алгоритма положены особенности работы устройства [1]. Поскольку преобразование входных данных и текущих состояний выполняется в следящем режиме, процесс вычислений имеет волновую природу, при этом его период Т зависит от разрядности обрабатываемых кодов n и определяется как Т=2n/f, где f тактовая частота квантования процесса. В обработку поступают входные данные в кодовом представлении N, N1, N2 (блоки 1, 2, 3) и начальное неопределенное значение выходного кода Nвых (блок 13). Эти коды попарно образуют положительную и отрицательную ветви процесса. В каждой ветви параллельно выполняется автономное преобразование данных для их представления во временной развертке. Один из кодов каждой ветви подвергается временной развертке (ВР), то есть представляется в виде последовательности информационных квантов, количество которых за период процесса соответствует обрабатываемому коду (блоки 4, 6). Второму коду ставится в соответствие относительная за период работы длительность некоторого действующего значения, что соответствует широтной развертке (ШР) (блоки 5, 7). При использовании ВР и ШР развертывающее умножение (РУ) заключается в использовании в процессе дальнейших вычислений только тех квантов первого кода, которые возникают в период действующего значения второго кода. Таким образом, на выходе блока 8 появиться поток квантов, количество которых за период работы устройства определяется как Nвых1=NN1 (блок 10), а на выходе блока 9 – поток соответствующий Nвых2=N2Nвых (блок 12). Полученные потоки квантов объединяются и группируются (блок 11) с выделением потока разности R=N1N2 – N3Nвых, который накапливается по периодам и может преобразовываться в код (блок 13). Благодаря замыканию структуры отрицательной обратной связью, ветви процесса приходят в равновесие, характеризующееся равенством интенсивностей потоков Nвых1 и Nвых2. Обеспечение условия R=0 соответствует устойчивому состоянию системы, а накопленное значение разности потоков определяет результат как Nвых=N N1/N2 . Алгоритм реализует операцию деления структурно, генерируя равновесную систему, причем некоторые параметры системы характеризуют результаты вычислений, выполняющихся в режиме слежения (блоки 10, 12, 13). Процесс, соответствующий такому алгоритму, “помнит” свое равновесное состояние, генетически заложенное в его структурной организации, и стремление к равновесию в любой момент развития процесса обеспечивает движение к результату и возвращение к нему после каких-либо нарушений.

Используя предлагаемые структурные методы выполнения базовых операций можно вычислять дробно-рациональные функции вида

Nвых=N(a0+a1N1+a2N12)/ (b0+b1N1+b2N12)

Для реализации преобразователей второй степени необходимо обеспечить одновременное развертывающее умножение двух кодов по правилам: умножение код N– код N1, код N – инверсный код N1, код N – тождественная единица. Структурная схема комбинированного развертывающего умножения приведена на рис. 2.

В отличие от умножения кодов при реализации множительно-делительной операции, потоком квантов временной развертки кода N (блоки 1, 3) управляет действующее значение кода N1 (блоки 2, 4) с одновременным формированием трех выходных квантовых потоков. На Р1 действующее значение кода N1 не оказывает влияния, поэтому он соответствует временной развертке кода N, что тождественно умножению кода N на 1 (блок 7). Второй поток Р2 соответствует относительной длительности действующего значения, управляется прерыванием от блока 4 (блок 5) и описывается выражением P2=NN1. Поток Р3 выделяется отсутствием действующего значения, управляется прерыванием от блока 4 (блок 6) и будет определяться как умножение на инверсный код P3=N(not N1).

Одна из возможных реализаций преобразователя связана с параллельно-рекурсивной комбинацией множительно-делительных операций. При этом коэффициенты аi, bi будут представлены кодами, а одночлены в числителе и знаменателе будут вычисляться в режиме развертывающего умножения. Второй способ выполнения преобразований связан с использованием весов vi, присваиваемых информационным потокам на этапе их объединения и группировки. Структурная схема процесса вычислений при использовании весовых потоков приведена на рис.3.

В обработку поступают значения N и N1 в кодовом представлении, а так же начальные выходные значения Nвых1, Nвых2 (блоки 1, 2). Выполняется широтная развертка кода N1 (блок 5) и временные развертки кодов N, Nвых1, Nвых2 (блоки 3, 4, 6), при выполнении следящего умножения в соответствии со схемой рис. 2 формируются 9 потоков данных: P1=Nвых1N1, P2=Nвых (not N1), P3=Nвых1, P4=NN1, P5=N(not N1), P6=N, P7=Nвых2N1, P8=Nвых(not N1), P9=Nвых2 (блоки 7, 8, 9). Эти потоки могут рассматриваться как результаты дополнительных операций, явно не связанных с видом дробно-рационального преобразования. Блок 10 соответствует группировке потоков, и распределению их в четыре ветви процесса

Vj=f(vj,i Рi),

где 1 ? j ? 4, 1 ? i ? 9, vj,i – вес потока Рi в ветви Vj.

Потоки разности ветвей V1 –V2 и V3 – V4, выделяемые в блоках 11, 12 накапливаются и в устойчивом состоянии процесса соответствуют кодовому эквиваленту результата (блоки 13, 14).

Рассмотрим пример построения алгоритмов рассматриваемого класса для получения косинусной зависимости

Nвых= N Cos(p N1), для чего воспользуемся дробно-рациональным приближением второй степени Nвых = N(-4 N12 + 1) / (N12 + 1).

Процесс вычисления будет происходить в соответствии со структурной схемой приведенной на рис.3. В начальный момент состояние системы равновесное неопределенное с непрерывным временным преобразованием кодов Nвых1 и Nвых2 (блоки 3, 6). При поступлении входных кодов N и N1 выполняется их временная и широтная раз вертка (блоки 4, 5) и выполняется развертывающее умножение. Для вычисления выбранной функции достаточно использовать следующий набор потоков: P1, P3, P4, P6, P7, P9, которые группируются в четыре ветви (блок 10) по следующим правилам

V1= v1,1P1 + v1,4 P4 , V2 = v2,9 P9,

V3 = v3,6 P6 , V4 = v4,7 P7+ v4,3P3.

На входе блоков 11 и 12 потокам присваиваются следующие веса:

v1,1 =1, v1,4 =4, v2,9 =2,

v3,6 =1, v4,7 =2, v4,3 =1.

Устройство стремится к равновесному состоянию, и установившийся режим будет характеризоваться равенством потоков по положительным и отрицательным ветвям блоков 11 и 12, что соответствует выполнению условий V1 –V2=0 V3 –V4=0.

Подставляя значения потоков с соответствующими весами в уравнение равновесия ветвей процесса, получим систему уравнений:

i Nвых1N1+4NN1–2Nвых2=0

i

i N-2Nвых2N1 –Nвых1 =0,

решением которой являются

Nвых1=N(-4N12+1)/(N12+1),

Nвых2=5NN12/(2N12+2).

Общий вид переходного процесса, полученный в результате моделирования алгоритма при разных наборах входных данных, приведен на рис 4. В первый момент процесс находится в неопределенном состоянии и при поступлении входных данных начинает движение к результату. Время переходного процесса зависит от входных данных и начального состояния.

Для получения дробно-рациональных зависимостей степени n потребуются: блок выполнения широтной развертки; n+1 блоков временных разверток и блоков развертывающего умножения, которые будут обеспечивающих формирование 3(n+1) потоков; блок перегруппировки потоков, объединяющий потоки в 2n ветвей процесса.

Предлагаемые принципы организации вычислительных алгоритмов, которым присущи генетические свойства, становятся возможными благодаря тому, что вычисление представляется не как событие, связанное с получением результата, а как непрерывный процесс его формирования. Если процесс обладает устойчивостью, а для конкретных наборов входных воздействий это можно определить заранее, то уже по поведению в начальный момент времени можно предположить характер переходного процесса и параметры устойчивого состояния, характеризующего результат.

Рассмотренные примеры построения вычислительных процессов по предлагаемым генетическим алгоритмам, подтверждают автоматическое восстановление результатов после сбоев.

Литература

1.Н.М. Сафьянников, О.И. Буренева. Множительно-делительное устройство. Патент РФ № 2097829 от 27.11.97. Опубл. БИ №3.


Site of Information Technologies
Designed by  inftech@webservis.ru.